package leetcode_周赛._2022._202211;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * @author yezh
 * @version 1.0
 * @date 2022/11/6 10:49
 */
public class _06 {

    public static void main(String[] args) {
        System.out.println(new _06().totalCost(new int[]{1, 2, 4, 1}, 3, 3));
    }

    /**
     * 6230. 长度为 K 子数组中的最大和
     * 算法：滑动窗口
     */
    public long maximumSubarraySum(int[] nums, int k) {
        long ans = 0, t = 0;
        int n = nums.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int l = 0, r = 0; r < n; r++) {
            // 新加的数在窗口中已经存在
            if (map.containsKey(nums[r])) {
                int idx = map.get(nums[r]);
                for (; l <= idx; l++) {
                    t -= nums[l];
                    map.remove(nums[l]);
                }
                l = idx + 1;
            }
            // 加上新的数后, 滑动窗口的大小大于 k
            if (r - l >= k) {
                t -= nums[l];
                map.remove(nums[l]);
                ++l;
            }
            t += nums[r];
            map.put(nums[r], r);
            if (map.size() == k) ans = Math.max(ans, t);
        }
        return ans;
    }

    /**
     * 6231. 雇佣 K 位工人的总代价
     * 算法：模拟 + 堆
     */
    public long totalCost(int[] costs, int k, int candidates) {
        int n = costs.length, l = candidates - 1, r = n - candidates;
        PriorityQueue<Integer> q1 = new PriorityQueue<>();
        PriorityQueue<Integer> q2 = new PriorityQueue<>();
        for (int i = 0; i <= l; i++) q1.offer(costs[i]);
        for (int i = Math.max(r, l + 1); i < n; i++) q2.offer(costs[i]);
        long ans = 0;
        for (int i = 0; i < k; i++) {
            Integer min1 = q1.peek(), min2 = q2.peek();
            int m1 = min1 == null ? Integer.MAX_VALUE : min1;
            int m2 = min2 == null ? Integer.MAX_VALUE : min2;
            if (m1 <= m2) {
                ans += m1;
                q1.poll();
                if (l < r - 1) q1.offer(costs[++l]);
            } else {
                ans += m2;
                q2.poll();
                if (l < r - 1) q2.offer(costs[--r]);
            }
        }
        return ans;
    }

}
